/**
 * @addtogroup BAS
 * @{
 * @file
 * List容器操作
 */
#include <assert.h>
#include <string.h>
#include "bas/bas_list.h"

static const char mcaId[] = "$Id$";

//取List的节点大小
#define _BAS_LIST_GET_NODESIZE(_ptList) (sizeof(T_ListNode) + (_ptList)->tTypeInfo.nTypeSize)

//取List迭代器指向的数据区
#define _BAS_LIST_ITER_GET_DATA(_tIterator) ((void *)(((T_ListNode *)(_tIterator).tPos.pvBasicPos)->caData))

//初始化列表尾节点(哨兵节点)
#define _BAS_LIST_END_NODE_INIT(_ptListEndNode)                                 \
        (_ptListEndNode)->ptPrev = (_ptListEndNode)->ptNext = (_ptListEndNode); \

//判断列表是否为空
#define _BAS_LIST_IS_EMPTY(_ptListEndNode)         \
    ((_ptListEndNode)->ptPrev == (_ptListEndNode)) \

//在_ptPosition之前插入_ptListNode
#define _BAS_LIST_NODE_INSERT_BEFORE(_ptListNode, _ptPosition) \
    do                                                         \
    {                                                          \
        (_ptListNode)->ptNext = (_ptPosition);                 \
        (_ptListNode)->ptPrev = (_ptPosition)->ptPrev;         \
        (_ptPosition)->ptPrev->ptNext = (_ptListNode);         \
        (_ptPosition)->ptPrev = (_ptListNode);                 \
    } while (false);                                           \

//在_ptPostion之后插入_ptListNode
#define _BAS_LIST_NODE_INSERT_AFTER(_ptListNode, _ptPosition) \
    do                                                        \
    {                                                         \
        (_ptListNode)->ptNext = (_ptPosition)->ptNext;        \
        (_ptListNode)->ptPrev = (_ptPosition);                \
        (_ptPosition)->ptNext->ptPrev = (_ptListNode);        \
        (_ptPosition)->ptNext = (_ptListNode);                \
    } while (false);                                          \

//删除节点_ptListNode
#define _BAS_LIST_NODE_DELETE(_ptListNode)                     \
    do                                                         \
    {                                                          \
        (_ptListNode)->ptPrev->ptNext = (_ptListNode)->ptNext; \
        (_ptListNode)->ptNext->ptPrev = (_ptListNode)->ptPrev; \
    } while (false);                                           \

static void _basListIteratorGetValue(const T_Iterator tIterator, void *pvValue);
static void *_basListIteratorGetPointer(const T_Iterator tIterator);
static void _basListIteratorSetValue(T_Iterator tIterator, const void * pvValue);
static T_Iterator _basListIteratorNext(const T_Iterator tIterator);
static T_Iterator _basListIteratorPrev(const T_Iterator tIterator);
static bool _basListIteratorEqual(const T_Iterator tFirstIterator, const T_Iterator tSecondIterator);

static void _basListInnerSwap(T_ListNode *ptFirst, T_ListNode *ptSecond);
static void _basListInnerMerge(T_ListNode *ptFirst, T_ListNode *ptSecond,
                               const T_TypeInfo *ptTypeInfo, const T_CompareFunction pfnLess);

//List迭代器回调函数表
static T_IteratorCallBackTable mtListIteratorCallBackTable =
    {NULL,  //T_IteratorIsValid not support
     _basListIteratorGetValue,
     _basListIteratorGetPointer,
     _basListIteratorSetValue,
     _basListIteratorNext,
     _basListIteratorPrev,
     _basListIteratorEqual,
     NULL,  //T_IteratorLessFunction not support
     NULL,  //T_IteratorNextNFunction not support
     NULL,  //T_IteratorPrevNFunction not support
     NULL}; //T_IteratorMinusFunction not support

BAS_EXPORT T_List *basListCreate(const T_TypeInfo tTypeInfo)
{
    T_List *ptList = NULL;

    if (NULL == (ptList = (T_List *)malloc(sizeof(T_List))))
    {
        CONTAINER_LOG_ERROR("malloc failed");
        return NULL;
    }
    memset(ptList, 0, sizeof(T_List));

    if (NULL == (ptList->ptEndNode = (T_ListNode *)malloc(sizeof(T_ListNode))))
    {
        CONTAINER_LOG_ERROR("malloc faild");
        free(ptList);
        return NULL;
    }
    memset(ptList->ptEndNode, 0, sizeof(T_ListNode));

    //迭代器回调函数表
    ptList->ptCallBackTable = &mtListIteratorCallBackTable;
    //类型信息
    memcpy(&ptList->tTypeInfo, &tTypeInfo, sizeof(ptList->tTypeInfo));

    //初始化List
    _BAS_LIST_END_NODE_INIT(ptList->ptEndNode);

    return ptList;
}

BAS_EXPORT void basListDestroy(T_List *ptList)
{
    if (NULL == ptList)
    {
        return;
    }

    basListResize(ptList, 0);
    free(ptList->ptEndNode);
    free(ptList);
}

BAS_EXPORT void basListClear(T_List *ptList)
{
    assert(ptList != NULL);

    basListResize(ptList, 0);
}

BAS_EXPORT size_t basListSize(const T_List *ptList)
{
    assert(ptList != NULL);

    size_t nSize = 0;

    for (T_ListNode *ptNode = ptList->ptEndNode->ptNext;
         ptNode != ptList->ptEndNode;
         ptNode = ptNode->ptNext)
    {
        ++nSize;
    }

    return nSize;
}

BAS_EXPORT int _basListResize(T_List *ptList, const size_t nSize, ...)
{
    assert(ptList != NULL);

    va_list varList;
    void *pvInitParameter = NULL;
    size_t nListSize = 0;
    void *pvBuff = NULL;

    //如果nSize小于List中当前的元素个数, 
    //则舍弃除了前nSize以后的所有元素, 并且调用销毁函数(如果有的话)
    nListSize = basListSize(ptList);
    if (nSize < nListSize)
    {
        for (int i = 0; i < nListSize - nSize; ++i)
            basListPopBack(ptList);
    }
    //如果nSize大于List中当前的元素个数, 多余的元素使用初始化函数进行初始化
    //(如果未指定初始化函数, 默认填0)
    else if (nSize > nListSize)
    {
        if (NULL == (pvBuff = (void *)malloc(ptList->tTypeInfo.nTypeSize)))
        {
            CONTAINER_LOG_ERROR("malloc failed");
            return -1;
        }
        memset(pvBuff, 0, ptList->tTypeInfo.nTypeSize);

        //如果指定了初始化函数
        if (ptList->tTypeInfo.pfnInit != NULL)
        {
            //取初始化参数
            va_start(varList, nSize);     
            if (BAS_PARM_END == (pvInitParameter = va_arg(varList, void *)))
            {
                pvInitParameter = NULL;
            }
            va_end(varList);
        }

        //初始化元素, 添加元素
        for (int i = 0; i < nSize - nListSize; ++i)
        {
            if (ptList->tTypeInfo.pfnInit != NULL)
            {
                if (ptList->tTypeInfo.pfnInit(pvBuff, pvInitParameter) != 0)
                {
                    CONTAINER_LOG_ERROR("pfnInit failed");
                    return -1;
                }
            }

            if (basListPushBack(ptList, pvBuff) != 0)
            {
                CONTAINER_LOG_ERROR("basListPushBack failed");
                return -1;
            }

            if (ptList->tTypeInfo.pfnDestroy != NULL)
            {
                ptList->tTypeInfo.pfnDestroy(pvBuff);
            }
        }

        free(pvBuff);
    }

    return 0;
}

BAS_EXPORT bool basListEmpty(const T_List *ptList)
{
    assert(ptList != NULL);

    //尾节点的前驱为尾节点自身时, List为空
    if (ptList->ptEndNode->ptPrev == ptList->ptEndNode)
    {
        assert(ptList->ptEndNode->ptNext == ptList->ptEndNode);
        return true;
    }
    else
    {
        return false;
    }
}

BAS_EXPORT int basListPushBack(T_List *ptList, ...)
{
    assert(ptList != NULL);

    T_ListNode *ptNewListNode = NULL;
    va_list varList;

    //新建新节点, 分配内存
    if (NULL ==
        (ptNewListNode = (T_ListNode *)malloc(_BAS_LIST_GET_NODESIZE(ptList))))
    {
        CONTAINER_LOG_ERROR("malloc failed");
        return -1;
    }
    memset(ptNewListNode, 0, _BAS_LIST_GET_NODESIZE(ptList));

    //根据数据类型从可变参数取值
    va_start(varList, ptList);
    if (_basContainerGetVaArgValue(&ptList->tTypeInfo, (void *)ptNewListNode->caData, &varList) != 0)
    {
        CONTAINER_LOG_ERROR("_basContainerGetVaArgValue failed");
        return -1;
    }
    va_end(varList);

    //在尾节点前插入元素
    _BAS_LIST_NODE_INSERT_BEFORE(ptNewListNode, ptList->ptEndNode);

    return 0; 
}

BAS_EXPORT void basListPopBack(T_List *ptList)
{
    assert(ptList != NULL);

    T_ListNode *ptNodeToDel = NULL;

    if (basListEmpty(ptList))
    {
        CONTAINER_LOG_WARN("list is empty");
        return;
    }

    //在尾节点前删除元素
    ptNodeToDel = ptList->ptEndNode->ptPrev;
    _BAS_LIST_NODE_DELETE(ptNodeToDel);

    //调用销毁函数(如果有的话)
    if (ptList->tTypeInfo.pfnDestroy != NULL)
    {
        (ptList->tTypeInfo.pfnDestroy)((void *)ptNodeToDel->caData);
    }

    free(ptNodeToDel);
}

BAS_EXPORT int basListPushFront(T_List *ptList, ...)
{
    assert(ptList != NULL);

    T_ListNode *ptNewListNode = NULL;
    va_list varList;

    //新建新节点, 分配内存
    if (NULL ==
        (ptNewListNode = (T_ListNode *)malloc(_BAS_LIST_GET_NODESIZE(ptList))))
    {
        CONTAINER_LOG_ERROR("malloc failed");
        return -1;
    }
    memset(ptNewListNode, 0, _BAS_LIST_GET_NODESIZE(ptList));
    //根据数据类型从可变参数取值
    va_start(varList, ptList);
    if (_basContainerGetVaArgValue(&ptList->tTypeInfo, (void *)ptNewListNode->caData, &varList) != 0)
    {
        CONTAINER_LOG_ERROR("_basContainerGetVaArgValue failed");
        return -1;
    }
    va_end(varList);

    //在尾节点后插入元素
    _BAS_LIST_NODE_INSERT_AFTER(ptNewListNode, ptList->ptEndNode);

    return 0; 
}

BAS_EXPORT void basListPopFront(T_List *ptList)
{
    assert(ptList != NULL);

    T_ListNode *ptNodeToDel = NULL;

    if (basListEmpty(ptList))
    {
        CONTAINER_LOG_WARN("list is empty");
        return;
    }

    //在尾节点后删除元素
    ptNodeToDel = ptList->ptEndNode->ptNext;
    _BAS_LIST_NODE_DELETE(ptNodeToDel);

    //调用销毁函数(如果有的话)
    if (ptList->tTypeInfo.pfnDestroy != NULL)
    {
        (ptList->tTypeInfo.pfnDestroy)((void *)ptNodeToDel->caData);
    }

    free(ptNodeToDel);
}

BAS_EXPORT T_Iterator basListBegin(const T_List *ptList)
{
    assert(ptList != NULL);

    T_Iterator tIterator;

    tIterator.tPos.pvBasicPos = (void *)ptList->ptEndNode->ptNext;
    tIterator.pvContainer = (void *)ptList;
    tIterator.eIteratorType = ITERATOR_BIDIRECTIONAL;
    tIterator.eContainerType = CONTAINER_LIST;

    return tIterator;
}

BAS_EXPORT T_Iterator basListEnd(const T_List *ptList)
{
    assert(ptList != NULL);

    T_Iterator tIterator;

    tIterator.tPos.pvBasicPos = (void *)ptList->ptEndNode;
    tIterator.pvContainer = (void *)ptList;
    tIterator.eIteratorType = ITERATOR_BIDIRECTIONAL;
    tIterator.eContainerType = CONTAINER_LIST;

    return tIterator;
}

BAS_EXPORT T_Iterator basListRBegin(const T_List *ptList)
{
    assert(ptList != NULL);

    T_Iterator tIterator;

    tIterator.tPos.pvBasicPos = (void *)ptList->ptEndNode->ptPrev;
    tIterator.pvContainer = (void *)ptList;
    tIterator.eIteratorType = ITERATOR_BIDIRECTIONAL;
    tIterator.eContainerType = CONTAINER_LIST;

    return tIterator;
}

BAS_EXPORT T_Iterator basListREnd(const T_List *ptList)
{
    assert(ptList != NULL);
    
    T_Iterator tIterator;

    tIterator.tPos.pvBasicPos = (void *)ptList->ptEndNode;
    tIterator.pvContainer = (void *)ptList;
    tIterator.eIteratorType = ITERATOR_BIDIRECTIONAL;
    tIterator.eContainerType = CONTAINER_LIST;

    return tIterator;
}

BAS_EXPORT T_Iterator basListInsert(T_List *ptList, const T_Iterator tIterator, ...)
{
    assert(ptList != NULL);    
    assert(basIteratorIsValid(tIterator));
    assert(ptList == (T_List *)tIterator.pvContainer);

    T_Iterator tNewIterator; //指向新插入元素的迭代器
    va_list varList;

    //新建新节点, 分配内存
    memcpy(&tNewIterator, &tIterator, sizeof(T_Iterator));
    if (NULL == (tNewIterator.tPos.pvBasicPos = (void *)malloc(_BAS_LIST_GET_NODESIZE(ptList))))
    {
        CONTAINER_LOG_ERROR("malloc failed");
        memset(&tNewIterator, 0, sizeof(T_Iterator));
        return tNewIterator;
    }
    memset(tNewIterator.tPos.pvBasicPos, 0, _BAS_LIST_GET_NODESIZE(ptList));
    //拷贝新元素
    va_start(varList, tIterator);
    if (_basContainerGetVaArgValue(&ptList->tTypeInfo, _BAS_LIST_ITER_GET_DATA(tNewIterator), &varList) != 0)
    {
        CONTAINER_LOG_ERROR("_basContainerGetVaArgValue failed");
        memset(&tNewIterator, 0, sizeof(T_Iterator));
        return tNewIterator;
    }
    va_end(varList);
    
    //在迭代器tIterator的位置前插入一个元素
    _BAS_LIST_NODE_INSERT_BEFORE((T_ListNode *)tNewIterator.tPos.pvBasicPos,
                                 (T_ListNode *)tIterator.tPos.pvBasicPos);

    return tNewIterator;
}

BAS_EXPORT T_Iterator basListErase(T_List *ptList, const T_Iterator tIterator)
{
    assert(ptList != NULL);
    assert(basIteratorIsValid(tIterator));
    assert(!basIteratorEqual(basListEnd(ptList), tIterator));
    assert(ptList == (T_List *)tIterator.pvContainer);

    T_Iterator tNewIterator = basIteratorNext(tIterator);

    //删除迭代器指向的元素
    _BAS_LIST_NODE_DELETE((T_ListNode *)tIterator.tPos.pvBasicPos);

    //调用销毁函数(如果有的话)
    if (ptList->tTypeInfo.pfnDestroy != NULL)
    {
        ptList->tTypeInfo.pfnDestroy(_BAS_LIST_ITER_GET_DATA(tIterator));    
    }

    free(tIterator.tPos.pvBasicPos);

    return tNewIterator;
}

BAS_EXPORT void _basListSort(T_List *ptList, ...)
{
#define _TEMP_COUNT 64 

    assert(ptList != NULL);

    va_list varList;
    T_CompareFunction pfnLess;
    T_ListNode tCarry;
    T_ListNode taTemp[_TEMP_COUNT];
    T_ListNode *ptFill = &taTemp[0];
    T_ListNode *ptCounter = NULL;

    //0个元素和1个元素的情况下直接返回
    if (ptList->ptEndNode->ptNext == ptList->ptEndNode ||
        ptList->ptEndNode->ptNext->ptNext == ptList->ptEndNode)
    {
        return;
    }

    //取小于比较函数
    va_start(varList, ptList);
    if (BAS_PARM_END == (pfnLess = va_arg(varList, T_CompareFunction)))
    {
        if (ptList->tTypeInfo.pfnLess != NULL)
        {
            pfnLess = ptList->tTypeInfo.pfnLess;
        }
        else
        {
            pfnLess = NULL;
        }
    }
    va_end(varList);

    _BAS_LIST_END_NODE_INIT(&tCarry);
    for (int i = 0; i < _TEMP_COUNT; ++i)
    {
        _BAS_LIST_END_NODE_INIT(&taTemp[i]);
    }

    //使用归并排序
    do
    {
        T_ListNode *ptNode = ptList->ptEndNode->ptNext;
        _BAS_LIST_NODE_DELETE(ptNode);
        _BAS_LIST_NODE_INSERT_BEFORE(ptNode, &tCarry);  

        for (ptCounter = &taTemp[0];
             ptCounter != ptFill && !_BAS_LIST_IS_EMPTY(ptCounter);
             ++ptCounter)
        {
           _basListInnerMerge(ptCounter, &tCarry, &ptList->tTypeInfo, pfnLess);
           _basListInnerSwap(&tCarry, ptCounter);
        }
        _basListInnerSwap(ptCounter, &tCarry);

        if (ptCounter == ptFill)
        {
            ++ptFill;
        }
    } while (!_BAS_LIST_IS_EMPTY(ptList->ptEndNode));

    for (ptCounter = &taTemp[1]; ptCounter != ptFill; ++ptCounter)
    {
        _basListInnerMerge(ptCounter, ptCounter - 1, &ptList->tTypeInfo, pfnLess);
    }

    _basListInnerSwap(ptList->ptEndNode, ptFill - 1);
}

/**
 * @brief    交换两个列表
 * @param[in] ptFirst    第一个列表的尾节点(哨兵节点)指针
 * @param[in] ptSecond   第二个列表的尾节点(哨兵节点)指针
 */
static void _basListInnerSwap(T_ListNode *ptFirst, T_ListNode *ptSecond)
{
    T_ListNode tFirstTemp = *ptFirst;
    T_ListNode tSecondTemp = *ptSecond;
    tFirstTemp.ptNext->ptPrev = ptSecond;
    tFirstTemp.ptPrev->ptNext = ptSecond;
    tSecondTemp.ptNext->ptPrev = ptFirst;
    tSecondTemp.ptPrev->ptNext = ptFirst;
    *(ptFirst) = tSecondTemp;
    *(ptSecond) = tFirstTemp;
    if (ptFirst->ptNext == ptSecond)
    {
        ptFirst->ptNext = ptFirst;
    }
    if (ptFirst->ptPrev == ptSecond)
    {
        ptFirst->ptPrev = ptFirst;
    }
    if (ptSecond->ptNext == ptFirst)
    {
        ptSecond->ptNext = ptSecond;
    }
    if (ptSecond->ptPrev == ptFirst)
    {
        ptSecond->ptPrev = ptSecond;
    }
}

/**
 * @brief     按照给定的小于比较函数归并两个列表, 结果放在第一个列表中
 * @param[in] ptTypeInfo 类型信息
 * @param[in] pfnLess    小于比较函数
 * @param[in] ptFirst    第一个列表的尾节点(哨兵节点)指针
 * @param[in] ptSecond   第二个列表的尾节点(哨兵节点)指针
 * @note      如果元素相等, 则第一个列表的元素在第二个之前, 且同一个列表中相等元素的次序保持不变
 */
static void _basListInnerMerge(T_ListNode *ptFirst, T_ListNode *ptSecond,
                               const T_TypeInfo *ptTypeInfo, const T_CompareFunction pfnLess)
{
    T_ListNode *ptFirstIter = ptFirst->ptNext;
    T_ListNode *ptFirstEnd = ptFirst;
    T_ListNode *ptSecondIter = ptSecond->ptNext;
    T_ListNode *ptSecondEnd = ptSecond;
    T_ListNode *ptNext = NULL;

    while (ptFirstIter != ptFirstEnd && ptSecondIter != ptSecondEnd)
    {
         if (pfnLess != NULL ? (pfnLess((void *)ptSecondIter->caData, (void *)ptFirstIter->caData))
                             : (memcmp((void *)ptSecondIter->caData, (void *)ptFirstIter->caData,
                                       ptTypeInfo->nTypeSize) < 0))
         {
            ptNext = ptSecondIter->ptNext;
            _BAS_LIST_NODE_DELETE(ptSecondIter);
            _BAS_LIST_NODE_INSERT_BEFORE(ptSecondIter, ptFirstIter);
            ptSecondIter = ptNext;
         }
         else
         {
            ptFirstIter = ptFirstIter->ptNext;
         }
    }

    while (ptSecondIter != ptSecondEnd)
    {
        ptNext = ptSecondIter->ptNext;
        _BAS_LIST_NODE_DELETE(ptSecondIter); 
        _BAS_LIST_NODE_INSERT_BEFORE(ptSecondIter, ptFirstIter);
        ptSecondIter = ptNext;
    }
}

/**
 * @brief List实现的basIteratorGetValue
 * @see   basIteratorGetValue
 */
static void _basListIteratorGetValue(const T_Iterator tIterator, void *pvValue)
{
    memcpy(pvValue, _BAS_LIST_ITER_GET_DATA(tIterator),
           _BAS_LIST_GET_NODESIZE((T_List *)tIterator.pvContainer));
}

/**
 * @brief List实现的basIteratorGetPointer
 * @see   basIteratorGetPointer
 */
static void *_basListIteratorGetPointer(const T_Iterator tIterator)
{
    return  _BAS_LIST_ITER_GET_DATA(tIterator);
}

/**
 * @brief List实现的basIteratorSetValue
 * @see   basIteratorSetValue
 */
static void _basListIteratorSetValue(T_Iterator tIterator, const void * pvValue)
{
    memcpy(_BAS_LIST_ITER_GET_DATA(tIterator), pvValue,
           _BAS_LIST_GET_NODESIZE((T_List *)tIterator.pvContainer));
}

/**
 * @brief List实现的basIteratorNext
 * @see   basIteratorNext
 */
static T_Iterator _basListIteratorNext(const T_Iterator tIterator)
{
    T_Iterator tIteratorNext;

    memcpy(&tIteratorNext, &tIterator, sizeof(T_Iterator));
    tIteratorNext.tPos.pvBasicPos = (void *)((T_ListNode *)tIteratorNext.tPos.pvBasicPos)->ptNext;

    return tIteratorNext;
}

/**
 * @brief List实现的basIteratorPrev
 * @see   basIteratorPrev
 */
static T_Iterator _basListIteratorPrev(const T_Iterator tIterator)
{
    T_Iterator tIteratorPrev;

    memcpy(&tIteratorPrev, &tIterator, sizeof(T_Iterator));
    tIteratorPrev.tPos.pvBasicPos = (void *)((T_ListNode *)tIteratorPrev.tPos.pvBasicPos)->ptPrev;

    return tIteratorPrev;
}

/**
 * @brief List实现的basIteratorEqual
 * @see   basIteratorEqual
 */
static bool _basListIteratorEqual(const T_Iterator tFirstIterator, const T_Iterator tSecondIterator)
{
    return tFirstIterator.tPos.pvBasicPos == tSecondIterator.tPos.pvBasicPos; 
}

/** @} */
